package niuke;
import java.util.*;
//class ListNode {
//    int val;
//    ListNode next = null;
//    public ListNode(int val){
//        this.val=val;
//    }
//  }
//class Interval {
//    int start;
//    int end;
//    Interval() { start = 0; end = 0; }
//    Interval(int s, int e) { start = s; end = e; }
//}
//public class niuKeMain {
//
//    public static int[] solve1 (int[] a) {
//        // write code here
//        Stack<Integer> stack1=new Stack<>();
//        int[] arr=new int[a.length];
//        int count=0;
//        int n=arr.length;
//        boolean[] vis=new boolean[n+10];
//        for(int i=0;i<a.length;i++){
//            stack1.push(a[i]);
//            vis[a[i]]=true;
//            while(n>0&&vis[n]==true){
//                n--;
//            }
//            while(!stack1.isEmpty()&&n<=stack1.peek()){
//                arr[count++]=stack1.pop();
//            }
//        }
//        while(!stack1.isEmpty()){
//            arr[count++]=stack1.pop();
//        }
//        return arr;
//    }
//    public String solve (int[] nums) {
//        // write code here
//        String[] str=new String[nums.length];
//        StringBuilder str1=new StringBuilder();
//        for(int i=0;i<nums.length;i++){
//            str[i]=String.valueOf(nums[i]);
//        }
//        Arrays.sort(str,new Comparator<String>(){
//            public int compare(String o1,String o2){
//                return Integer.valueOf(o2+o1)-Integer.valueOf(o1+o2);
//            }
//        });
//        if(str[0].equals("0")){
//            return "0";
//        }
//        for(int i=0;i<nums.length;i++){
//            str1.append(str[i]);
//        }
//        return str1.toString();
//    }
//    public ListNode oddEvenList (ListNode head) {
//        // write code here
//        if(head==null){
//            return null;
//        }
//        ListNode head1=new ListNode(-1);
//        ListNode n1=head1;
//        ListNode head2=new ListNode(-1);
//        ListNode n2=head2;
//        int count=1;
//        while(head!=null){
//            if(count%2==1){
//                n1.next=head;
//                n1=n1.next;
//                head=head.next;
//            }
//            else{
//                n2.next=head;
//                n2=n2.next;
//                head=head.next;
//            }
//            count++;
//        }
//        n1.next=head2.next;
//        n2.next=null;
//        return head1.next;
//    }
//
//    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
//        ArrayList<Interval> arrayList=new ArrayList<>();
//        int count=0;
//        if (intervals==null){
//            return null;
//        }
//        PriorityQueue<Interval> queue=new PriorityQueue<>(new Comparator<Interval>() {
//            @Override
//            public int compare(Interval o1, Interval o2) {
//                return o1.start-o2.start;
//            }
//        });
//        for (Interval one:intervals) {
//            queue.offer(one);
//        }
//        while (!queue.isEmpty()){
//            Interval interval=queue.poll();
//            if(arrayList.isEmpty()){
//                arrayList.add(interval);
//                count++;
//            }
//            else {
//                Interval interval1=arrayList.get(count-1);
//                if(interval1.end>=interval.start&&interval1.end<=interval.end){
//                    arrayList.remove(--count);
//                    interval1.end=interval.end;
//                    arrayList.add(interval1);
//                    count++;
//                }
//                else if(interval1.end>interval.start&&interval1.end>interval.end){
//                    continue;
//                }
//                else {
//                    arrayList.add(interval);
//                    count++;
//                }
//            }
//        }
//        return arrayList;
//    }
//    public ListNode sortInList (ListNode head) {
//        if(head==null){
//            return null;
//        }
//        PriorityQueue<ListNode> queue=new PriorityQueue<>(new Comparator<ListNode>() {
//            @Override
//            public int compare(ListNode o1, ListNode o2) {
//                return o1.val- o2.val;
//            }
//        });
//        ListNode head1=head;
//        while (head1!=null){
//            queue.offer(head1);
//            head1=head1.next;
//        }
//        ListNode head2=new ListNode(-1);
//        ListNode n1=head2;
//        while (!queue.isEmpty()){
//            n1.next=queue.poll();
//            n1=n1.next;
//        }
//        n1.next=null;
//        return head2.next;
//    }
//    public  void medianOfThree(int[] array,int left,int right) {
//        int mid=(left+right)/2;
//        if(array[mid] < array[left]) {
//            int tmp = array[mid];
//            array[mid] = array[left];
//            array[left] = tmp;
//        }//array[mid] <= array[start]
//        if(array[left] > array[right]) {
//            int tmp = array[left];
//            array[left] = array[right];
//            array[right] = tmp;
//        }//array[start] <= array[right]
//        if(array[mid] > array[right]) {
//            int tmp = array[mid];
//            array[mid] = array[right];
//            array[right] = tmp;
//        }
//    }
//    public  int partition(int[] array, int start, int end){
//        int tmp = array[start];
//        while (start < end) {
//            while (start < end && array[end] >= tmp) {
//                end--;
//            }
//            array[start] = array[end];
//            while (start < end && array[start] <= tmp) {
//                start++;
//            }
//            array[end] = array[start];
//        }
//        array[start] = tmp;
//        return start;
//    }
//    public void quick(int[] array,int left,int right){
//        if(left>=right){
//            return ;
//        }
//        medianOfThree(array,left,right);
//        int pivot=partition(array,left,right);
//        quick(array,left, pivot-1);
//        quick(array,pivot+1, array.length-1);
//    }
//    public void quickSort(int[] array){
//        quick(array,0, array.length-1);
//    }
//    public int findKth(int[] a, int n, int K) {
//        // write code here
//        quickSort(a);
//        return a[n-K];
//    }
//    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
//        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2-o1;
//            }
//        });
//        ArrayList<Integer> arrayList=new ArrayList<>();
//        if(input==null){
//            return arrayList;
//        }
//        for (int i = 0; i < input.length; i++) {
//            if(i<k){
//                queue.offer(input[i]);
//            }
//            else {
//                if (queue.peek()>input[i]){
//                    queue.poll();
//                    queue.offer(input[i]);
//                }
//                else if (queue.peek()==input[i]){
//                    queue.offer(input[i]);
//                }
//            }
//        }
//        for (int i = 0; i < k&&!queue.isEmpty(); i++) {
//            arrayList.add(queue.poll());
//        }
//        return arrayList;
//    }
//    public static void main(String[] args) {
//
//    }
//}
